package com.hgx.algorithm.base.niukewang;

import java.util.Scanner;

/**
 * 给定一个无序数组，包含正数、负数和0，要求从中找出3个数的乘积，使得乘积最大，要求时间复杂度：O(n)，空间复杂度：O(1)
 */
public class MaximumProduct {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int size = in.nextInt();
        int[] arr = new int[size];
        for (int i = 0; i < size; i++) {
            arr[i] = in.nextInt();
        }
        System.out.println(getMostMaxByArrayThreeNumber(arr));
    }

    private static long getMostMaxByArrayThreeNumber(int[] arr) {

        if (arr.length <= 3) {

            if (arr.length == 3) {
                return arr[0] * arr[1] * arr[2];
            } else {
                try {
                    throw new Exception("数组的长度小于3");
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
        }

        int mostMax = 0;
        int secondMax = 0;
        int threeMax = 0;
        int mostMin = 0;
        int secondMin = 0;

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != 0) {
                if (arr[i] > mostMax) {
                    threeMax = secondMax;
                    secondMax = mostMax;
                    mostMax = arr[i];
                } else if (arr[i] > secondMax) {
                    threeMax = secondMax;
                    secondMax = arr[i];
                } else if (arr[i] > threeMax) {
                    threeMax = arr[i];
                } else if (arr[i] < mostMin) {
                    secondMin = mostMin;
                    mostMin = arr[i];
                } else if (arr[i] > mostMin && arr[i] < secondMin) {
                    secondMin = arr[i];
                }
            } else {
                continue;
            }
        }
        return (long) mostMax * secondMax * threeMax > (long) mostMax * secondMin * mostMin ? (long) mostMax * secondMax * threeMax : (long) mostMax * secondMin * mostMin;
    }
}